Міністерство освіти і науки, молоді та спорту України
Національний Університет «Львівська Політехніка»
кафедра АСУ
Звіт
до лабораторної роботи №5
на тему: Двоїстість задач лінійного програмування
з дисципліни:
«Математичні методи дослідження операцій»
Лабораторна робота №5
Тема: Двоїстість задач лінійного програмування
Мета: Навчитись складати та розв’язувати двоїсті задачі лінійного програмування симплекс методом.
Хід роботи
1.Короткі теоретичні відомості:
1.1 Двоїстий симплекс метод
Для переходу до двоїстої задачі позначимо y1, y2, y3 – ціну одиниці часу роботи на токарному, фрезерному і свердлильному станках: (yi>0).
Тоді
витрати на виробництво Fmin(y) при умові, що сумарні затрати на одиницю продукції не менше вартості товару.
Обмеження
1.2 Алгоритм запису двоїстої задачі:
1. Коефіцієнти цільової функції прямої задачі с1,с2,…,сn стають вільними членами обмежень двоїстої задачі.
Вільні члени обмежень прямої задачі b1,b2,…,bn стають коефіцієнтами цільової функції двоїстої задачі.
Матрицю обмежень двоїстої задачі отримують транспонуванням матриці обмежень прямої задачі.
Число змінних двоїстої задачі рівне числу обмежень прямої, а число обмежень двоїстої рівне числу змінних прямої, і навпаки.
Взаємно однозначна відповідність між змінними прямої задачі і обмеженнями двоїстої:
j-е обмеження двоїстої задачі буде нерівністю, якщо на j-у змінну прямої задачі накладена вимога невід’ємності, а в іншому випадку – j-е обмеження буде рівністю.
1.3 Приклади запису двоїстих умов
№1
№2
2. Розв`язування задачі
2.1 Індивідуальне завдання
Завдання:(83)
F(x1,x2) = 6x1 -4x2 -> max;
5x1 + 2x2 >=10,
2x1 + 5x2 >=10,
-2x1 + x2 <=4,
6<=x1>= 0, 6<=x2 >= 0.
2.2 Графічний метод рішення прямої задачі (ОДЗ, градієнт, мах(х1,х2), мін(х1,х2))
/
/
2.3 Симплекс-метод рішення прямої задачі (пакет SimplexWin)
Крок 0
Базис
БП
x1
x2
x3
x4
x5
x6
x7
z1
z2
z1
10
5
2
-1
0
0
0
0
1
0
z2
10
2
5
0
-1
0
0
0
0
1
x5
4
-2
1
0
0
1
0
0
0
0
x6
6
1
0
0
0
0
1
0
0
0
x7
6
0
1
0
0
0
0
1
0
0
ІР
-20M
-7M-6
-7M+4
M
M
0
0
0
0
0
Крок 1
Базис
БП
x1
x2
x3
x4
x5
x6
x7
z1
z2
x1
2
1
2/5
-1/5
0
0
0
0
1/5
0
z2
6
0
21/5
2/5
-1
0
0
0
-2/5
1
x5
8
0
9/5
-2/5
0
1
0
0
2/5
0
x6
4
0
-2/5
1/5
0
0
1
0
-1/5
0
x7
6
0
1
0
0
0
0
1
0
0
ІР
-6M+12
0
-21/5M+32/5
-2/5M-6/5
M
0
0
0
7/5M+6/5
0
Крок 2
Базис
БП
x1
x2
x3
x4
x5
x6
x7
z1
z2
x1
10/7
1
0
-5/21
2/21
0
0
0
5/21
-2/21
x2
10/7
0
1
2/21
-5/21
0
0
0
-2/21
5/21
x5
38/7
0
0
-4/7
3/7
1
0
0
4/7
-3/7
x6
32/7
0
0
5/21
-2/21
0
1
0
-5/21
2/21
x7
32/7
0
0
-2/21
5/21
0
0
1
2/21
-5/21
ІР
20/7
0
0
-38/21
32/21
0
0
0
M+38/21
M-32/21
Крок 3
Базис
БП
x1
x2
x3
x4
x5
x6
x7
z1
z2
x1
5
1
5/2
0
-1/2
0
0
0
0
1/2
x3
15
0
21/2
1
-5/2
0
0
0
-1
5/2
x5
14
0
6
0
-1
1
0
0
0
1
x6
1
0
-5/2
0
1/2
0
1
0
0
-1/2
x7
6
0
1
0
0
0
0
1
0
0
ІР
30
0
19
0
-3
0
0
0
M
M+3
Крок 4
Базис
БП
x1
x2
x3
x4
x5
x6
x7
z1
z2
x1
6
1
0
0
0
0
1
0
0
0
x3
20
0
-2
1
0
0
5
0
-1
0
x5
16
0
1
0
0
1
2
0
0
0
x4
2
0
-5
0
1
0
2
0
0
-1
x7
6
0
1
0
0
0
0
1
0
0
ІР
36
0
4
0
0
0
6
0
M
M
X=(6,0,20,2,16,0,6);
F(max)=6*6=36;
2.4 Запис умов двоїстої задачі і її рішення симплекс-методом (пакет SimplexWin)
Умова двоїстої задачі буде виглядати так:
-5y1-2y2-2y3+y4>=6;
2y1+5y2-y3-y5,=4;
-10y1-10y2+4y3+6y4+6y5 -> min
Крок 0
Базис
БП
y 1
y 2
y 3
y 4
y 5
y 6
y 7
y 8
y8
6
-5
-2
-2
1
0
-1
0
1
y7
4
2
5
-1
0
-1
0
1
0
КР
6M
10-5M
10-2M
-4...
